1207. sqrt log sin

 

An evil professor has just assigned you the following problem. A sequence is defined by the following recurrence: 

x0 = 1,

xi =   +  +

For each value i compute the value xi​.

 

Input. Consists of multiple lines. Each line contains one integer – the value of i, which is not less than 0 and not more than 106. The last line contains -1 and is not processed.

 

Output. For each value of i (except the last -1) print the corresponding value of xi, calculated by modulo 106.

 

Sample input

Sample output

0

1

2

10

-1

1

3

5

21

 

 

SOLUTION

recurrent relation

 

Algorithm analysis

The value of xi will be calculated by means of the function f(i). To do it we must implement the recurrence

 =   +  + ,

with memoization of f(i) in a linear array dp of size 106.

 

Algorithm realization

Store the values xi in array dp.

 

#define MAX 1000001

int dp[MAX];

 

Function f(n) finds the value of xn.

 

int f(int n)

{

 

Terminate the recursion when n = 0.

 

  if (n == 0) return 1;

 

If xn is already found (x[n] ≠ -1), return its value.

 

  if (dp[n] != -1) return dp[n];

 

Calculate recursively the first, second and third summand.

 

  int a = f((int)(n - sqrt(n)));

  int b = f((int)(log(n)));

  int c = f((int)(n * sin(n) * sin(n)));

 

Find, memoize and return the value of xn.

 

  return dp[n] = (a + b + c) % 1000000;

}

 

The main part of the program. Set x[i] = -1, if the value of xi is not found. Read the input value of n and print the answer.

 

memset(dp,-1,sizeof(dp));

while(scanf("%d",&n), n != -1)

  printf("%d\n",f(n));

 

Algorithm realization – nonrecursive

 

#include <stdio.h>

#include <math.h>

 

int i, n;

int x[1000001];

 

int main(void)

{

  x[0] = 1;

  for (i = 1; i <= 1000000; i++)

    x[i] = (x[(int)(i - sqrt(i))] + x[(int)(log(i))] +

            x[(int)(i * sin(i) * sin(i))]) % 1000000;

 

  while (scanf("%d", &n), n != -1)

    printf("%d\n", x[n]);

  return 0;

}

 

Java realization

 

import java.util.*;

 

public class Main

{

  static int dp[] = new int[1000001];

 

  static int f(int n)

  {

    if (n == 0) return 1;

    if (dp[n] != -1) return dp[n];

   

    int a = f((int)(n - Math.sqrt(n)));

    int b = f((int)(Math.log(n)));

    int c = f((int)(n * Math.sin(n) * Math.sin(n)));

    return dp[n] = (a + b + c) % 1000000;

  }

 

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    Arrays.fill(dp, -1);

    while(true)

    {

      int n = con.nextInt();

      if (n == -1) break;

      System.out.println(f(n));

    }

    con.close();

  }

}